package com.example.question.dp.dp1;

public class Code12_44 {


    public static void main(String[] args) {
        Code12_44 code = new Code12_44();
//        boolean match1 = code.isMatch1("bbaaabaabbabaaababbaabbbabbaababbbbbaabbbbabbbbaaa", "aa*******ba***b*******");
//        System.out.println(match1);
        boolean match2 = code.isMatch("b", "??");
        System.out.println(match2);
    }


    public boolean isMatch1(String s, String p) {
        Boolean[][] dp = new Boolean[s.length()][p.length()];
        return dfs(s, s.length() - 1, p, p.length() - 1, dp);
    }

    /**
     * 先来个暴力递归
     * 超出时间限制
     */
    private boolean dfs(String s, int i, String p, int j, Boolean[][] dp) {
        if (j < 0 && i < 0) {
            return true;
        }
        if (i >= 0 && j >= 0 && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
            if (dp[i][j] != null) {
                return dp[i][j];
            }
            boolean dfs = dfs(s, i - 1, p, j - 1, dp);
            dp[i][j] = dfs;
            return dfs;
        } else if (j >= 0 && p.charAt(j) == '*') {
            if (j == 0) {
                return true;
            }
            // 还有可能就是 i已经是-1给匹配完了
            int index = Math.max(i, 0);
            for (int k = 0; k <= index; k++) {
                boolean dfs = dfs(s, i - k, p, j - 1, dp);
//                if (dp[i][j] == null) {
//                } else {
//                    dfs = dp[i][j];
//                }
                if (dfs) {
                    return true;
                }
            }
        }
        return false;
    }

    // dp[i][j] 表示s前i个字符和p的去前j个字符是否匹配
    //  acdcb
    //  a*c?b

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        char[] chars1 = s.toCharArray();
        char[] chars2 = p.toCharArray();
        if (m == 0) {
            if (n == 0) {
                return true;
            } else {
                for (char c : chars2) {
                    if (c != '*') {
                        return false;
                    }
                }
            }
            return true;
        }
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int row = 1; row < m + 1; row++) {
            dp[row][0] = false;
        }

        // 注意边界条件
        for (int col = 1; col < n + 1; col++) {
            if (chars2[col - 1] == '*') {
                dp[0][col] = dp[0][col - 1];
            } else {
                dp[0][col] = false;
            }
        }

        for (int row = 1; row < m + 1; row++) {
            for (int col = 1; col < n + 1; col++) {
                if (chars1[row - 1] == chars2[col - 1] || chars2[col - 1] == '?') {
                    dp[row][col] = dp[row - 1][col - 1];
                } else if (chars2[col - 1] == '*') {
                    dp[row][col] = dp[row - 1][col] || dp[row][col - 1];
                } else {
                    dp[row][col] = false;
                }
            }
        }
        return dp[m][n];
    }
}

